// Huffman.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

/*******************************************************************
 *  File Name: Huffman.c
 *  Description: Main file of the Huffman encode and decode procedure
 *
 *      The Huffman Algothrim Needs Frequecy Tree, So I Don't Split the
 *      Encode and Decode Procedure into Two Files.
 *		
 *		This project is composed of the following 3 files:
 *		- Huffman.cpp		this file, the main logic
 *		- bitstream.h		function related to the bitstream operation 
 *							(decode and encode write and read)
 *		- structures.h		the main data structures definitions
 *
 *
 *  Date: 2019-10-18 21:36:33
 *  Auther: Zhipeng Xu
 *  Last Modified: 2019-11-16 20:36:40
 ******************************************************************/

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <process.h>
#include <io.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <sys/timeb.h>
#include <sys/utime.h>
#include <Windows.h>
#include "structures.h"
#include "bitstream.h"
#define FILELEN 0x100

/* Changed Chinese into English just for convenience while loading binary file */
const char* filename = "Nobel_Prize_in_Chemistry.txt";

const size_t symbolcnt = 0x100;
void checkencoding(Freqperchar** freqp);

int main(int argc, char const* argv[])
{

	/* Prompt the user to enter the filename */
	char* user_input = (char*)malloc(sizeof(char) * FILELEN), * lf = user_input;
	printf("Please input the filename to Encode and Decode using the Huffman Algorithm:\n");
	printf("[Default: %s](Just Press Enter)\n", filename);
	fgets(user_input, FILELEN, stdin);
	while (*lf != '\n') lf++;
	*lf = 0;
	if (lf != user_input) filename = user_input;
	printf("Your input filename is %s\n", filename);


	/* Step 1 - read in the binay file to be encoded */
	struct stat filestat;
	if (stat(filename, &filestat) != 0) err((char *)"File Does Not Exist!\n");
	size_t filelength = filestat.st_size;
	char* filecontent = (char*)malloc(filelength * sizeof(char) + 1);
	if (!filecontent) err((char*)"Malloc error!\n");
	

	FILE* fp;
	errno_t err = fopen_s(&fp, filename, "rb");
	fread(filecontent, sizeof(char), filelength, fp);
	fclose(fp);
	printf("Successfully Opened %s, size: %lu Bytes\n", filename, (long unsigned)filelength);


	/* Step 2 - collect frequency per byte */
	size_t i;
	Freqperchar freq[symbolcnt], * freqp[symbolcnt];
	/* Initialize the frequency array (in frequency order)
	 and the corresponding pointer array (in alphabetical order) */
	for (i = 0; i < symbolcnt; i++) {
		freq[i].c = (unsigned char)i;
		freq[i].cnt = 0;
		freq[i].encodebits = 0;
		freq[i].code = 0;
		freqp[i] = &freq[i];
	}
	LARGE_INTEGER t1, t2, tc;
	QueryPerformanceFrequency(&tc);
	QueryPerformanceCounter(&t1);
	/* loop the array to collect occurance counts */
	for (i = 0; i < filelength; i++)
		freq[(unsigned char)filecontent[i]].cnt++;
	/* sort the frequency array from small to large */
	qsort(freq, symbolcnt, sizeof(Freqperchar), sortbycnt);
	qsort(freqp, symbolcnt, sizeof(Freqperchar*), sortbyc);


	/* Step 3 - filter out chars that occurs zero times and make a linked list and a tree */
	Freqperchar* fptr = freq, * eptr = &freq[symbolcnt - 1];
	while (!fptr->cnt) fptr++;
	/* make the head node of the entire list */
	ListNode* listhead = (ListNode*)malloc(sizeof(ListNode));
	listhead->cnt = 0;
	listhead->tree = NULL;
	listhead->next = NULL;

	/* insert linked node in the reverse order */
	for (; fptr <= eptr; eptr--) {
		ListNode* newlistnode = (ListNode*)malloc(sizeof(ListNode));
		newlistnode->next = listhead->next;
		newlistnode->cnt = eptr->cnt;
		TreeNode* newtreenode = (TreeNode*)malloc(sizeof(TreeNode));
		newtreenode->cnt = eptr->cnt;
		newtreenode->leaf = eptr;
		newtreenode->left = NULL;
		newtreenode->right = NULL;
		newlistnode->tree = newtreenode;
		listhead->next = newlistnode;
	}


	/* Step 4 - Implement Huffman Algorithm */
	while (listhead->next && listhead->next->next) {
		ListNode* first = listhead->next;
		ListNode* second = first->next;
		size_t cnt = first->cnt + second->cnt;
		ListNode* insert = second;
		while (insert->next && insert->next->cnt <= cnt) /* points to the node before insertion */
			insert = insert->next;
		/* create a new listnode and delete the original two */
		ListNode* newlistnode = (ListNode*)malloc(sizeof(ListNode));
		newlistnode->next = insert->next;
		newlistnode->cnt = cnt;
		TreeNode* newtreenode = (TreeNode*)malloc(sizeof(TreeNode));
		newtreenode->cnt = cnt;
		newtreenode->leaf = NULL;
		newtreenode->left = first->tree;
		newtreenode->right = second->tree;
		newlistnode->tree = newtreenode;
		insert->next = newlistnode;
		listhead->next = second->next;
		free(first);
		free(second);
	}
	/* once finished, there will be only one node in the list, with the pointer to the tree */
	const TreeNode* tree = listhead->next->tree;
	size_t encodedlength = 0;
	assigncode(tree, 0 /* initial level 0 */, 0 /* initial code 0 */, &encodedlength);
	

	/* Step 5 - prepare the file buffer for write & setup the bitstream structure */
	size_t bufhufflen = (encodedlength + 7) / 8;
	printf("Encoded File Size: %lu Btyes\n", (unsigned long)bufhufflen);
	printf("Compress Rate: %lf%%\n", bufhufflen / (double)filelength * 100);
	unsigned char* bufhuff = (unsigned char*)malloc(bufhufflen);
	BitStream* bs = bsnew(bufhuff, bufhufflen);
	for (i = 0; i < filelength; i++)
		bswritec(bs, freqp[(unsigned char)filecontent[i]]);
	QueryPerformanceCounter(&t2);
	printf("Assign Huffman Code & Encode Used :%fms\n", (t2.QuadPart - t1.QuadPart) * 1000.0 / tc.QuadPart);
	printf("Encode Speed :%fms / KB\n", (t2.QuadPart - t1.QuadPart) * 1000.0 / tc.QuadPart / filelength * 8 * 1024);
	/* Prompt the user to choose whether to show the Huffman tree or not */
	printf("Encode Finished, Print Encode List? [Default: No](Just Press Enter)\n");
	printf("[y/n] ");
	char inputc = getc(stdin);
	fflush(stdin);
	if (inputc == 'y' || inputc == 'Y')
		checkencoding(freqp);


	/* Step 6 - write back the encoded file */
	char* encodedfilename = (char*)malloc(sizeof(char) * FILELEN * 2);
	char* encoded_prefix = (char*)"[Encoded_Huffman]";
	strncpy_s(encodedfilename, FILELEN * 2, filename, FILELEN);
	strncat_s(encodedfilename, FILELEN * 2, encoded_prefix, strlen(encoded_prefix) + 1);
	err = fopen_s(&fp, encodedfilename, "wb");
	if (fwrite(bufhuff, sizeof(char), bufhufflen, fp) != 0)
		printf("Encoded File %s Written Successfuly\n", encodedfilename);
	else
		printf("Encoded File %s Written Failed\n", encodedfilename);
	fclose(fp);


	/* Step 7 - decode */
	char* decodebuf = (char*)malloc(filelength * sizeof(char) + 1);
	/* reset the bitstream */
	bs->ptr = bs->base;
	bs->offset = 0;
	for (i = 0; i < filelength; i++)
		decodebuf[i] = (char)(bsgetc_huff(bs, tree)->c);


	/* Step 8 - write back decoded file*/
	char* decodedfilename = (char*)malloc(sizeof(char) * FILELEN * 2);
	char* decoded_prefix = (char*)"[Decoded_Huffman]";
	strncpy_s(decodedfilename, FILELEN * 2, filename, FILELEN);
	strncat_s(decodedfilename, FILELEN * 2, decoded_prefix, strlen(decoded_prefix) + 1);
	err = fopen_s(&fp, decodedfilename, "wb");
	if (fwrite(decodebuf, sizeof(char), filelength, fp) != 0)
		printf("Decoded File %s Written Successfuly\n", decodedfilename);
	else
		printf("Decoded File %s Written Failed\n", decodedfilename);
	fclose(fp);


	/* Step 9 - Compress Rate in Theory */
	double srcentropy = 0;
	for (i = 0; i < symbolcnt; i++) {
		double p = freq[i].cnt / (double)filelength;
		if (p < 1e-10) continue;
		srcentropy -= p * log2(p);
	}
	printf("Source Entropy per Symbol = %lf\n", srcentropy);
	printf("Maximum Compress Rate In Theroy: %lf%%\n", srcentropy / 8 * 100);


	/* Final Step - Clean up the memory */
	free(user_input);
	free(filecontent);
	free(listhead);
	free(bufhuff);
	free(encodedfilename);
	free(decodebuf);
	free(decodedfilename);
	return 0;
}

void checkencoding(Freqperchar** freqp)
{
	size_t i;
	int j;
	printf("SYMBOL\tCODELEN\tCODE\n");
	for (i = 0; i < symbolcnt; i++) {
		if (freqp[i]->encodebits == 0) continue;
		printf("0x%02lx\t%d\t",
			(long unsigned int)freqp[i]->c,
			freqp[i]->encodebits);
		for (j = freqp[i]->encodebits; j >= 0; j--)
			printf("%d", (unsigned int)(freqp[i]->code >> j) & 1);
		putchar('\n');
	}
}